package leetcode;

/*
590. N叉树的后序遍历
给定一个 N 叉树，返回其节点值的后序遍历。
例如，给定一个 3叉树 :
返回其后序遍历: [5,6,3,2,4,1].
*/

import java.util.ArrayList;
import java.util.List;

public class problems_590 {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node3.children = new ArrayList<Node>(){{
            add(node5);
            add(node6);
        }};
        node1.children = new ArrayList<Node>(){{
            add(node2);
            add(node3);
            add(node4);
        }};
        System.out.println(new Solution().postorder(node1));
    }

    static class Node {
        public int val;
        public List<Node> children;
        public Node() {}
        public Node(int _val) { val = _val; }
        public Node(int _val, List<Node> _children) { val = _val;children = _children; }
    }
    static class Solution {
        List<Integer> ret = new ArrayList<>();
        public List<Integer> postorder(Node root) {
            dfs(root);
            return ret;
        }
        private void dfs(Node node){
            if(null == node) return ;
            if (null != node.children) for (int i = 0; i < node.children.size(); i++) {
                dfs(node.children.get(i));
            }
            ret.add(node.val);
        }
    }
}